#pragma once

#include <initializer_list>
#include <iostream>

template <typename T>
class Node
{
public:
    T value;
    Node *next;

    Node(const T &value = T(), Node *next = nullptr) : next(next), value(value) {}

    ~Node()
    {
        if (next != nullptr)
        {
            delete next;
            next = nullptr;
        }
    }
};

template <typename T>
class Array
{
protected:
    Node<T> *head;
    int Size;

    Node<T> *previous(Node<T> *n) { return getNode(indexOf(n->value) - 1); }

    Node<T> *getNode(int i)
    {
        Node<T> *p = head;
        for (int j = 0; j < Size; j++)
        {
            if (j == i)
            {
                return p;
            }
            p = p->next;
        }
        return nullptr;
    }

    Node<T> *nodeOf(T value)
    {
        Node<T> *p = head;
        for (int i = 0; i < Size; i++)
        {
            if (p->value == value)
            {
                return p;
            }
            p = p->next;
        }
        return p;
    }

public:
    Array() : head(nullptr), Size(0) {}
    Array(const int Size, const T &t = T()) : Size(Size)
    {
        head = new Node<T>(t);
        Node<T> *p = head;
        for (int i = 1; i < Size; i++)
        {
            p->next = new Node<T>(t);
            p = p->next;
        }
    }
    Array(std::initializer_list<T> l) : Size(l.size())
    {
        auto j = l.begin();
        head = new Node<T>(*j++);
        Node<T> *p = head;
        for (int i = 1; i < Size; i++)
        {
            p->next = new Node<T>(*j++);
            p = p->next;
        }
    }
    Array(const Array &arr) : Size(arr.size())
    {
        head = (arr.empty() ? nullptr : new Node<T>(arr[0]));
        Node<T> *p = head;
        for (int i = 1; i < Size; i++)
        {
            p->next = new Node<T>(arr[i]);
            p = p->next;
        }
    }

    T &operator[](int i)
    {
        Node<T> *p = head;
        while (i > 0)
        {
            if (p->next == nullptr)
            {
                p->next = new Node<T>;
                Size++;
            }
            p = p->next;
            i--;
        }
        return p->value;
    }
    T operator[](int i) const
    {
        Node<T> *p = head;
        while (i > 0)
        {
            p = p->next;
            i--;
        }
        return p->value;
    }

    void operator=(const Array &arr)
    {
        Array tmp(arr);
        head = tmp.head;
    }

    bool operator==(const Array &arr)
    {
        Node<T> *p = head;
        if (Size != arr.size())
        {
            return false;
        }
        for (int i = 0; i < Size; i++)
        {
            if ((*this)[i] != arr[i])
            {
                return false;
            }
        }
        return true;
    }

    friend std::ostream &operator<<(std::ostream &out, const Array<T> &arr)
    {
        out << "[";
        for (int i = 0; i < arr.size(); i++)
        {
            out << arr[i] << " ";
        }
        out << "\b]";
        return out;
    }

    void insert(int i, T value)
    {
        Node<T> *q = new Node<T>(value);
        if (i == 0)
        {
            q->next = head;
            head = q;
        }
        else
        {
            Node<T> *p = getNode(i - 1);
            q->next = p->next;
            p->next = q;
        }
        Size++;
    }

    int indexOf(T value)
    {
        for (int i = 0; i < Size; i++)
        {
            if ((*this)[i] == value)
            {
                return i;
            }
        }
        return -1;
    }

    T pop()
    {
        if (Size == 0)
        {
            return 0;
        }
        if (Size == 1)
        {
            delete head;
            head = nullptr;
        }
        Node<T> *p = getNode(Size - 2);
        T value = p->next->value;
        delete p->next;
        p->next = nullptr;
        Size--;
        return value;
    }

    void append(T value)
    {
        Node<T> *q = new Node<T>(value);
        if (Size == 0)
        {
            head = q;
        }
        else
        {
            Node<T> *p = getNode(Size - 1);
            p->next = q;
        }
        Size++;
    }

    bool kill(T value)
    {
        if (Size == 0)
        {
            return false;
        }
        Node<T> *p = nodeOf(value);
        if (p == nullptr)
        {
            return false;
        }
        Node<T> *q = previous(p);
        (q == nullptr ? head = head->next : q->next = p->next);
        p->next = nullptr;
        delete p;
        p = nullptr;
        Size--;
        return true;
    }

    bool remove(int i)
    {
        if (i + 1 > Size)
        {
            return false;
        }
        Node<T> *tmp, *p;
        if (i == 0)
        {
            tmp = head;
            head = head->next;
        }
        else
        {
            p = getNode(i - 1);
            tmp = p->next;
            p->next = tmp->next;
        }
        tmp->next = nullptr;
        delete tmp;
        tmp = nullptr;
        Size--;
        return true;
    }

    int size() const { return Size; }
    bool empty() const { return (head == nullptr) ? true : false; }

    void clean()
    {
        if (head->next != nullptr)
        {
            delete head->next;
            head->value = 0;
        }
    }

    ~Array()
    {
        delete head;
        head = nullptr;
    }
};